{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7906c0a2-d29f-49c0-897b-13f8bc6bacff",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/letter-case-permutation/\n",
    "\n",
    "\n",
    "Runtime: 48 ms, faster than 92.99% of Python3 online submissions for Letter Case Permutation.\n",
    "Memory Usage: 14.7 MB, less than 77.03% of Python3 online submissions for Letter Case Permutation.\n",
    "\n",
    "\n",
    "```python\n",
    "from itertools import combinations\n",
    "import string\n",
    "\n",
    "class Solution:\n",
    "    def letterCasePermutation(self, S: str) -> List[str]:\n",
    "        #6:41\n",
    "        index_list = []\n",
    "        s = S.lower()\n",
    "        for i, char in enumerate(s):\n",
    "            if char in string.ascii_lowercase:\n",
    "                index_list.append(i)\n",
    "        result = []\n",
    "        for i in range(len(index_list)+1):\n",
    "            for possibility in combinations(index_list, i):\n",
    "                raw = list(s)\n",
    "                for j in possibility:\n",
    "                    raw[j] = raw[j].upper()  \n",
    "                raw = \"\".join(raw)\n",
    "                result.append(raw)\n",
    "        return result\n",
    "        #6:51\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "38cd1bc5-69b8-48c2-b96a-45851bafa8fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "l = [1,2,3,4,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "d1200346-c74c-4d83-836a-d680fd39e0de",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2, 3),\n",
       " (1, 2, 4),\n",
       " (1, 2, 5),\n",
       " (1, 3, 4),\n",
       " (1, 3, 5),\n",
       " (1, 4, 5),\n",
       " (2, 3, 4),\n",
       " (2, 3, 5),\n",
       " (2, 4, 5),\n",
       " (3, 4, 5)]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(combinations(l, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "8bf0b8f5-51da-48f6-94f8-34f02d06822b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, 3, 4]]"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def my_combinations(l, length_limit):\n",
    "    result = []\n",
    "    \n",
    "    def loop(current_list, index):\n",
    "        if index < len(l)-1:\n",
    "            current_list.append([l[index]])\n",
    "            for i in range(len(current_list)):\n",
    "                current_list[i].append(l[index])\n",
    "            loop(current_list.copy(), index+1)\n",
    "        else:\n",
    "            for e in current_list:\n",
    "                if len(e) == length_limit:\n",
    "                    result.append(e)    \n",
    "                \n",
    "    loop([], 0)\n",
    "    return result\n",
    "        \n",
    "my_combinations(l, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f459cdf-4da8-44e9-8893-ddaf1c80b07a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3a56434a-f4c3-4cb0-a254-8a4a48ae69fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [1,2,3,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "4e04dc6b-fee9-4ef8-9ec3-9b3cee18859d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "from pprint import pprint\n",
    "\n",
    "list(combinations(l, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "21807c76-7b0b-427d-8d6c-74fe88831d06",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l[:2] + l[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "bc37240e-d75a-48aa-adee-4a71e8627621",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[1, 2, 4]\n",
      "[1, 3, 2]\n",
      "[1, 3, 4]\n",
      "[1, 4, 2]\n",
      "[1, 4, 3]\n",
      "[2, 1, 3]\n",
      "[2, 1, 4]\n",
      "[2, 3, 1]\n",
      "[2, 3, 4]\n",
      "[2, 4, 1]\n",
      "[2, 4, 3]\n",
      "[3, 1, 2]\n",
      "[3, 1, 4]\n",
      "[3, 2, 1]\n",
      "[3, 2, 4]\n",
      "[3, 4, 1]\n",
      "[3, 4, 2]\n",
      "[4, 1, 2]\n",
      "[4, 1, 3]\n",
      "[4, 2, 1]\n",
      "[4, 2, 3]\n",
      "[4, 3, 1]\n",
      "[4, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "def my_combinations(source_list, length_limit):\n",
    "    result = []\n",
    "    \n",
    "    def loop(l, n, left_list):\n",
    "        if n == length_limit:\n",
    "            return \n",
    "        for i, e in enumerate(left_list):\n",
    "            new = l+[e]\n",
    "            if len(new) == length_limit:\n",
    "                result.append(new)\n",
    "                print(new)\n",
    "            loop(new, n+1, left_list[:i] + left_list[i+1:])\n",
    "            \n",
    "    loop([], 0, source_list)\n",
    "    \n",
    "    #print(result)\n",
    "    #return result\n",
    "\n",
    "my_combinations(l, 3)\n",
    "\n",
    "# shit, I have accidentally written a permutation algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "7b14dc84-b003-418b-90e9-83122ce2f517",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2, 3),\n",
       " (1, 2, 4),\n",
       " (1, 3, 2),\n",
       " (1, 3, 4),\n",
       " (1, 4, 2),\n",
       " (1, 4, 3),\n",
       " (2, 1, 3),\n",
       " (2, 1, 4),\n",
       " (2, 3, 1),\n",
       " (2, 3, 4),\n",
       " (2, 4, 1),\n",
       " (2, 4, 3),\n",
       " (3, 1, 2),\n",
       " (3, 1, 4),\n",
       " (3, 2, 1),\n",
       " (3, 2, 4),\n",
       " (3, 4, 1),\n",
       " (3, 4, 2),\n",
       " (4, 1, 2),\n",
       " (4, 1, 3),\n",
       " (4, 2, 1),\n",
       " (4, 2, 3),\n",
       " (4, 3, 1),\n",
       " (4, 3, 2)]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "list(permutations(l, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8da6dca0-cba8-4383-b6bf-eb4d50a744a8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "a34ea499-3eeb-43db-9ef0-f1b5aea4eaf2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[1, 2, 4]\n",
      "[1, 3, 4]\n",
      "[2, 3, 4]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def my_combinations(source_list, length_limit):\n",
    "    result = []\n",
    "    \n",
    "    def loop(l, n, left_list):\n",
    "        if n == length_limit:\n",
    "            return \n",
    "        for i, e in enumerate(left_list):\n",
    "            new = l+[e]\n",
    "            if len(new) == length_limit:\n",
    "                result.append(new)\n",
    "                print(new)\n",
    "            loop(new, n+1, left_list[i+1:])\n",
    "            \n",
    "    loop([], 0, source_list)\n",
    "    \n",
    "    #return result\n",
    "\n",
    "l = [1,2,3,4]\n",
    "my_combinations(l, 3)\n",
    "\n",
    "# shit, I just spent 2 minutes to turn the permutation algorithm to combination algorithm. great!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "853e847e-5545-4250-9709-3d75d9b7f2de",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(combinations(l, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3da489e9-85ac-4226-af1f-f76c8a1af3e8",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}